#ifndef TREE_H__
#define TREE_H__

#include <stdio.h>
#include <stdlib.h>

//#define ElemType char      //存储元素类型

typedef struct BinaryTreeNode
{
	char data;
	struct BinaryTreeNode *leftchild;
	struct BinaryTreeNode *rightchild;
} BinaryTreeNode;

typedef struct BinaryTree
{
	BinaryTreeNode *root;
	char refvalue; //stop flag
} BinaryTree;

void Init(BinaryTree *bt, char ref);
void Create(BinaryTree *bt);
void Create_(BinaryTree *bt, BinaryTreeNode **root);
void Create4(BinaryTree *tree, char **str);
void Create4_(BinaryTree *tree, BinaryTreeNode **root, char **str);
void Create_VLR_LVR(BinaryTreeNode ** node,char * VLR,char * LVR,int n);
void Create_LVR_LRV(BinaryTreeNode ** node,char * VLR,char * LRV,int n);
void PreOrder(BinaryTree *);
void PreOrder_(BinaryTreeNode *);
void InOrder(BinaryTree *);
void InOrder_(BinaryTreeNode *);
void PostOrder(BinaryTree *);
void PostOrder_(BinaryTreeNode *);
int Size(BinaryTree *); //求二叉树的结点个数
int Size_(BinaryTreeNode *);
int Height(BinaryTreeNode *); //求二叉树的高度
BinaryTreeNode *Search(BinaryTreeNode *, char key);
BinaryTreeNode *Parent(BinaryTreeNode *, BinaryTreeNode *);
BinaryTreeNode *LeftChild(BinaryTreeNode *p);
BinaryTreeNode *RightChild(BinaryTreeNode *p);
int Empty(BinaryTree *);
void Copy(BinaryTreeNode *, BinaryTreeNode **); //拷贝一棵树
void Clear(BinaryTreeNode **);
//==============================================================
//非递归的遍历方式
void _PreOrder(BinaryTreeNode *);
void _InOrder(BinaryTreeNode *);
int _PostOrder(BinaryTreeNode *);

#endif